package day001;

/**
 * 带备忘录(memorandum)的斐波那契数列，时间复杂度为O(N)
 * 自顶向下
 */
public class FibonacciSequence {
    public static void main(String[] args) {
        System.out.println(fib(10));
    }

    static int fib(int n) {
        if (n == 0) return 0;
        int[] memo = new int[n + 1];
        return helper(memo, n);
    }

    private static int helper(int[] memo, int n) {
        if (n == 1 || n == 2) return 1;
        if (memo[n] != 0) return memo[n];
        return memo[n] = helper(memo, n - 1) + helper(memo, n - 2);
    }
}
